This invention relates generally to multi-processor environments, and more particularly to avoiding deadlocks when performing storage updates in a multi-processor environment.
In a multiprocessing system where a consistent memory usage model is required, memory usage among different processors is managed using cache coherency ownership schemes. These schemes usually involve various ownership states for a cache line. These states include read-only (or commonly known as shared), and exclusive (where a certain processor has the sole and explicit update rights to the cache line, sometimes known as store access).
For one such protocol used for a strongly-ordered memory consistency model, as in IBM's z/Architecture implemented by IBM System z processors, when a processor is requesting rights to update a line, e.g. when it is executing a “Store” instruction, it will check its local cache (L1) for the line's ownership state. If the processor finds out that the line is either currently shared or is not in its cache at all, it will then send an “exclusive ownership request” to the storage controller (SC) which serves as a central coherency manager.
The storage controller (SC) tracks which processor, if any, currently owns a line exclusively. If deemed necessary SC will then send a specific “cross interrogate” (XI) or “ownership change” request to another processor which currently owns that line to release its exclusive rights. This XI is usually called an “exclusive XI”. Once the current owning processor has responded to the XI and responded that the exclusive ownership is released, the requesting processor will then be given exclusive update rights to the line requested.
It is also possible that the SC finds one or more processors currently have the requested line in a read-only (or shared) state. The SC will have to inform those processors through its XI interface, in this case indicating to those processors that the line is about to be changed. These processors' local cache logic will then make sure the data which currently exists in their caches cannot be consumed anymore.
In a large Symmetric Multi-Processing (SMP) system, it is common that various processes running on different processors, or different threads within a processor, update or use the same cache lines, at similar times. When a process running on one processor references or updates a line that is currently owned exclusively by another processor, the owning processor must acknowledge the XI and relinquish exclusive ownership before the first processor can access that line.
In some implementations a processor may in some cases reject an exclusive XI request and retain exclusive access to that line, in which case the storage controller will reprioritize its pending requesters and resend the exclusive XI at a later time. In this case, it is important that the owning processor does not retain exclusive access to that line indefinitely if it at the same time is also requesting a line from the storage controller in order to complete its current instruction, otherwise a deadlock may result.